package two.prefixSum_difference;

/**
 * 统计「优美子数组」
 * 前缀和、数组计数代码模板
 */
public class NumberOfSubarrays {
    //时间复杂度：O(n)

    //思路：如下
    //nums = [1,1,2,1,1] ==> nums = [1,1,0,1,1];==>题目转化为：求有多少个连续子数组（字段），字段和为k（使用前缀和）
    //暴力：O(n^2)
    //for r = 1 ~ n
    //  for l = 1 ~ r #[l,r]这个字段
    //      if s[r] - s[l] == k;
    //          ans += 1;
    //优化：先把r,l两个循环变量分离 O(n)
    //固定外层循环变量r，考虑内层满足什么条件
    //对于每个r(1~n)，考虑有几个l（1~r)，使得s[r]-s[l-1]=k
    //对于每个i(1~n)，考虑有几个j（0~r-1)，使得s[i]-s[j]=k
    //对于每个i(1~n)，考虑有几个j（0~r-1)，使得s[j]=s[i]-k
    //对于每个i，有几个s[j]等于s[i]-k
    //在一个数组s中，统计等于“某个值”（s[i]-k）的数（s[j]）的数量（count）
    //具体步骤：
    //1）使用前缀和，所以下标要变为1~n
    //2）初始化前缀和数组s
    //3）初始化计数数组count：长度为n的计数数组count（因为s最大值为n）
    //4）枚举：对于每个i，有几个s[j]等于s[i]-k
    //5）计数：s=[0, 1, 2, 2, 2, 3, 4] ==> count=[1, 1, 3, 3, 3, 1, 1] （1个0，1个1，3个2,3个2,3个2,1个3,1个4）注意：不要越界

    public static int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] s = new int[n + 1]; // 前缀和数组s，下标变为0、1~n
        int[] count = new int[n + 1]; //计数数组count
        //s[0] = 0;
        count[s[0]]++;
        for(int i = 1; i <= n; i++){
            s[i] = s[i - 1] + nums[i - 1] % 2; //2）初始化前缀和数组s
            count[s[i]]++; //3）初始化计数数组count：长度为n的计数数组count（因为s最大值为n）
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){ //4）枚举：对于每个i，有几个s[j]等于s[i]-k
            if(s[i] - k >= 0){
                ans += count[s[i] - k]; ////5）计数
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,2,1,2,2,1,2,2,2};
        int ans = numberOfSubarrays(nums, 2);
        System.out.println(ans);
    }
}
